﻿#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
	string longestPalindrome(string s) {
		int n = s.length();
		
		vector<vector<bool>> f(n, vector<bool>(n, false));
		
		int maxlen = 1, st = 0;
		
		for (int i = 0; i < n; i++) {
			f[i][i] = true;
		}

		for (int len = 2; len < n;len++) {
			for (int i = 0; i < len;i++) {
				int j = i + len - 1;
				if (j >= n) break;
				if (s[i] != s[j]) continue;
				if (!f[i + 1][j - 1]) continue;
				f[i][j] = true;
				
				maxlen = len;
				st = i;
			}
		}
		return s.substr(st, maxlen);
	}
};

int main() {
	Solution solution;
	string input = "babad";
	string result = solution.longestPalindrome(input);
	cout << result << endl;
	return 0;
}